package LeetCode;

public class _206 {


    public ListNode reverseList(ListNode head) {
        if(head ==  null || head.next == null)
            return head;
        ListNode pre =null,cur = head,post=head.next;
        while (cur != null) {
            post = cur.next;
            cur.next = pre;
            pre = cur;
            cur = post;
        }
        return pre;
    }
    /**
     * 迭代版本1，有个缺点是第一个节点单独处理了。其实可以不单独处理的，参见“迭代版本2“。
     * @param head
     * @return
     */
    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode pre = head, cur = head.next, post = head.next.next;
        pre.next = null;
        while (cur != null) {
            post = cur.next;
            cur.next = pre;
            pre = cur;
            cur = post;
        }
        return pre;
    }

    /**
     * 递归第二版本
     *
     * @param head
     * @return
     */
    public ListNode reverseListRecursive(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode res = reverseListRecursive(head.next);
        head.next.next = head;
        head.next = null;
        return res;

    }

    /**
     * 最初版本。设置一个返回将head反转的方法，其返回值是反转后的链表头节点和为尾节点组成的数组
     * [head, tail]
     *
     * @param head
     * @return
     */
    private ListNode[] reverseListHelper(ListNode head) {
        if (head == null || head.next == null)
            return new ListNode[]{head, head};
//        System.out.println(head);
        ListNode[] res = reverseListHelper(head.next);
        ListNode tmp_head = res[0], tmp_tail = res[1];
        tmp_tail.next = head;
        head.next = null;
        tmp_tail = head;
        return new ListNode[]{tmp_head, tmp_tail};
    }

    public static void main(String[] args) {
        int i, n = 4;
        long start, end;
        double time;
        int[] arr = new int[n];
        for (i = 0; i < n; i++) {
            arr[i] = i;
        }
        ListNode listNode = new ListNode(arr);
        _206 solution = new _206();


        start = System.nanoTime();
        for (i = 0; i < n; i++)
            solution.reverseList(listNode);
        end = System.nanoTime();
        time = (end - start) / 1e9;
        System.out.println("Iteration time: " + time);

        start = System.nanoTime();
        for (i = 0; i < n; i++)
            solution.reverseListRecursive(listNode);
        end = System.nanoTime();
        time = (end - start) / 1e9;
        System.out.println("Recursive time: " + time);
    }

}
